package hot_100;

import com.sun.source.tree.Tree;

import java.util.*;

/**
 * @author: Darven
 * @createTime: 2025-10-03  17:11
 * @description: TODO
 */
public class P94 {

    // 递归
//    public List<Integer> inorderTraversal(TreeNode root) {
//        List<Integer> ans = new ArrayList<>();
//        iterable(ans,root);
//        return ans;
//    }
//
//    private void iterable(List<Integer> list, TreeNode root){
//        if(root==null){
//            return;
//        }
//
//        iterable(list, root.left);
//        list.add(root.val);
//        iterable(list, root.right);
//
//    }

    // 迭代，使用队列
    public List<Integer> inorderTraversal(TreeNode root) {
        Deque<TreeNode> queue=new ArrayDeque<>();
        List<Integer> ans=new ArrayList<>();

        while (root!=null||!queue.isEmpty()){
            while (root!=null){
                queue.push(root);
                root=root.left;
            }
            root=queue.pop();
            ans.add(root.val);
            root=root.right;
        }
        return ans;
    }
}
